package com.base.dp;

import java.util.Arrays;

public class FindNumberOfLIS {
    public static void main(String[] args) {
        FindNumberOfLIS findNumberOfLIS = new FindNumberOfLIS();
        System.out.println(findNumberOfLIS.findNumberOfLIS(new int[]{2,2,2,2,2}));
    }
    public int findNumberOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        int[] length = new int[n];  // 初始化长度数组  length[i]表示以nums[i]结尾的最长递增子序列的长度
        int[] count = new int[n];   // 初始化计数数组  count[i]表示以nums[i]结尾的最长递增子序列的个数。
        int maxLen = 1;             // 最长递增子序列的长度
        int ans = 0;                // 最长递增子序列的个数
        // int []{1,2,3,4,5,6}
        // dp  []{1,2,3,2,1,1,1}   i=3
        //count[]{1,1,1,3,1,1,1}
        for (int i = 0; i < n; i++) {
            length[i] = 1;
            count[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    // 为什么就想不到呢？没有想到要判断length[i] < length[j] + 1，为什么没有想到这里呢，因为我没有办法记录每次最多的次数
                    // 谁知道这里就是解题的地方
                    // 当前i的长度小于 当前j的长度+1，那么表示找到了更长的子序列
                    if (length[i] < length[j] + 1) {
                        //则更新length[i] = length[j] + 1，并且count[i] = count[j]，因为在i前面找到了一个更长的递增子序列。
                        length[i] = length[j] + 1;
                        //这个就是第一次
                        count[i] = count[j];
                    } else if (length[i] == length[j] + 1) {
                        //length[i] == length[j] + 1，则说明找到了相同长度的递增子序列，因此count[i] += count[j]。
                        count[i] += count[j];
                    }
                }
            }
            maxLen = Math.max(maxLen, length[i]);
        }

        for (int i = 0; i < n; i++) {
            if (length[i] == maxLen) {
                ans += count[i];
                break;
            }
        }

        return ans;

    }
}
